package ljl.codetop300;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * 输入：s = "(1+(4+5+2)-3)+(6+8)"
 * 输出：23
 * <p>
 * 正常解法不会做
 */
public class _224_calculate {

  /**
   * 老宫解法1
   */
  static class leaves3 {
    public static void main(String[] args) {
      System.out.println(new leaves3().calculate("-2+1"));
    }
    public int calculate(String s) {
      Deque<Integer> nums = new ArrayDeque<>();
      nums.addLast(0);
      s = s.replaceAll(" ", "");
      Deque<Character> ops = new ArrayDeque<>();
      int n = s.length();
      char[] cs = s.toCharArray();
      for (int i = 0; i < n; i++) {
        char c = cs[i];
        // 左括号有必要入栈
        if (c == '(') {
          ops.addLast(c);
        }
        // 右括号和之前左括号之间的内容需要计算
        else if (c == ')') {
          while (!ops.isEmpty()) {
            char op = ops.peekLast();
            if (op != '(') {
              calc(nums, ops);
            } else {
              ops.pollLast();
              break;
            }
          }
        } else {
          // 数字入栈
          if (isNum(c)) {
            int u = 0;
            int j = i;
            while (j < n && isNum(cs[j])) u = u * 10 + cs[j++] - '0';
            nums.addLast(u);
            i = j - 1;
          }
          // 处理运算符
          else {
            // 这个很关键，处理两个运算符挨着的情况；通过插入一个 0，比如 -1，转化成了 0 - 1
            if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
              nums.addLast(0);
            }
            while (!ops.isEmpty() && ops.peekLast() != '(') calc(nums, ops);
            ops.addLast(c);
          }
        }
      }
      // 之前只有括号才会计算，现在处理一遍没括号的情况
      while (!ops.isEmpty()) calc(nums, ops);
      return nums.peekLast();
    }

    void calc(Deque<Integer> nums, Deque<Character> ops) {
      if (nums.isEmpty() || nums.size() < 2) return;
      if (ops.isEmpty()) return;
      int b = nums.pollLast(), a = nums.pollLast();
      char op = ops.pollLast();
      nums.addLast(op == '+' ? a + b : a - b);
    }

    boolean isNum(char c) {
      return Character.isDigit(c);
    }
  }

  /**
   */
  static class copy_1 {

    public static void main(String[] args) {
      System.out.println(new copy_1().calculate("1+1"));
    }

    Deque<Integer> nums = new LinkedList<>();
    Deque<Character> ops = new LinkedList<>();

    char[] chars;
    int len;
    public int calculate(String s) {
      s = s.replace(" ", "");
      chars = s.toCharArray();
      len = chars.length;
      nums.push(0);

      for (int i = 0; i < len; i++) {
        char c = chars[i];
        switch (c) {
          case '(' -> ops.push(c);
          case ')' -> {
            while (!ops.isEmpty()) {
              if (ops.peek() == '(') {
                ops.pop();
                break;
              } else {
                calc();
              }
            }
          }
          default -> {
            if (Character.isDigit(c)) {
              int num = 0;
              while (i < len && Character.isDigit(s.charAt(i))) {
                num = num * 10 + s.charAt(i) - '0';
                i++;
              }
              i--;
              nums.push(num);
            } else {
              char last = i > 0 ? chars[i - 1] : 0;
              if (last == '+' || last == '-' || last == '(') nums.push(0);
              while (!ops.isEmpty() && ops.peek() != '(') calc();
              ops.push(c);
            }
          }
        }
      }
      while (!ops.isEmpty()) {
        calc();
      }
      return nums.pop();
    }
    void calc() {
      if (nums.size() < 2) return;
      char op = ops.pop();
      int right = nums.pop();
      int left = nums.pop();
      nums.push(op == '+' ? left + right : left - right);
    }

  }

  /**
   * 老宫解法2
   */
  static class leaves3_2 {
    Map<Character, Integer> map = new HashMap<>(){{
      put('-', 1);
      put('+', 1);
      put('*', 2);
      put('/', 2);
      put('%', 2);
      put('^', 3);
    }};
    public int calculate(String s) {
      s = s.replaceAll(" ", "");
      char[] cs = s.toCharArray();
      int n = s.length();
      Deque<Integer> nums = new ArrayDeque<>();
      nums.addLast(0);
      Deque<Character> ops = new ArrayDeque<>();
      for (int i = 0; i < n; i++) {
        char c = cs[i];
        if (c == '(') {
          ops.addLast(c);
        } else if (c == ')') {
          while (!ops.isEmpty()) {
            if (ops.peekLast() != '(') {
              calc(nums, ops);
            } else {
              ops.pollLast();
              break;
            }
          }
        } else {
          if (isNumber(c)) {
            int u = 0;
            int j = i;
            while (j < n && isNumber(cs[j])) u = u * 10 + (cs[j++] - '0');
            nums.addLast(u);
            i = j - 1;
          } else {
            if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
              nums.addLast(0);
            }
            while (!ops.isEmpty() && ops.peekLast() != '(') {
              char prev = ops.peekLast();
              if (map.get(prev) >= map.get(c)) {
                calc(nums, ops);
              } else {
                break;
              }
            }
            ops.addLast(c);
          }
        }
      }
      while (!ops.isEmpty() && ops.peekLast() != '(') calc(nums, ops);
      return nums.peekLast();
    }
    void calc(Deque<Integer> nums, Deque<Character> ops) {
      if (nums.isEmpty() || nums.size() < 2) return;
      if (ops.isEmpty()) return;
      int b = nums.pollLast(), a = nums.pollLast();
      char op = ops.pollLast();
      int ans = 0;
      if (op == '+') {
        ans = a + b;
      } else if (op == '-') {
        ans = a - b;
      } else if (op == '*') {
        ans = a * b;
      } else if (op == '/') {
        ans = a / b;
      } else if (op == '^') {
        ans = (int)Math.pow(a, b);
      } else if (op == '%') {
        ans = a % b;
      }
      nums.addLast(ans);
    }
    boolean isNumber(char c) {
      return Character.isDigit(c);
    }
  }

  static class withMulDiv {

    public static void main(String[] args) {
      System.out.println(new withMulDiv().calculate("1 + 2*3"));
    }
    static Map<Character, Integer> map = new HashMap<>();
    static {
      map.put('+', 1);
      map.put('-', 1);
      map.put('*', 2);
      map.put('/', 2);
    }
    Deque<Character> ops = new LinkedList<>();
    Deque<Integer> nums = new LinkedList<>();
    char[] chars;
    int len;
    public int calculate(String s) {
      s = s.replace(" ", "");
      chars = s.toCharArray();
      len = s.length();
      nums.push(0);
      for (int i = 0; i < len; i++) {
        char c = chars[i];
        switch (c) {
          case '(' -> ops.push(c);
          case ')' -> {
            while (!ops.isEmpty()) {
              if (ops.peek() == '(') {
                ops.pop();
                break;
              }
              calc();
            }
          }
          default -> {
            if (Character.isDigit(c)) {
              int num = 0;
              while (i < len && Character.isDigit(chars[i])) {
                num = num * 10 + chars[i++] - '0';
              }
              i--;
              nums.push(num);
            } else {
              char last = i == 0 ? 0 : chars[i - 1];
              if (last == '(' || last == '+' || last == '-') {
                nums.push(0);
              }
              while (!ops.isEmpty() && ops.peek() != '(') {
                if (map.get(c) <= map.get(ops.peek())) {
                  calc();
                } else break;
              }
              ops.push(c);
            }
          }
        }
      }
      while (!ops.isEmpty()) calc();
      return nums.peek();
    }
    void calc() {
      if (nums.size() < 2) return;
      int right = nums.pop();
      int left = nums.pop();
      char op = ops.pop();
      switch (op) {
        case '+' -> nums.push(left + right);
        case '-' -> nums.push(left - right);
        case '*' -> nums.push(left * right);
        case '/' -> nums.push(left / right);
      }
    }

  }

  /**
   * 他这个解法非常巧妙
   * 他观察到只有正负号了，没有运算符优先级问题，每个数都是正常算，只是把符号进行入栈，用来处理括号的情况
   * 一开始符号是正数，栈里也有一个
   * 如果遇到正号，我要拿到总的符号；不能啥也不干，因为刚才可能是符号，但总的符号是正数
   * 总的符号就是假设整体在一个无形的括号里
   * 如果遇到括号，则把当前总的括号入栈
   */
  static class f {
    public int calculate(String s) {
      Deque<Integer> ops = new LinkedList<>();
      ops.push(1);
      int sign = 1;

      int ret = 0;
      int n = s.length();
      int i = 0;
      while (i < n) {
        if (s.charAt(i) == ' ') {
          i++;
        } else if (s.charAt(i) == '+') {
          sign = ops.peek();
          i++;
        } else if (s.charAt(i) == '-') {
          sign = -ops.peek();
          i++;
        } else if (s.charAt(i) == '(') {
          ops.push(sign);
          i++;
        } else if (s.charAt(i) == ')') {
          ops.pop();
          i++;
        } else {
          long num = 0;
          while (i < n && Character.isDigit(s.charAt(i))) {
            num = num * 10 + s.charAt(i) - '0';
            i++;
          }
          ret += sign * num;
        }
      }
      return ret;
    }
  }

  static class copyf {
    public static void main(String[] args) {
      System.out.println(new copyf().calculate("(1+(4+5+2)-3)+(6+8)"));
    }

    public int calculate(String s) {
      Deque<Integer> stack = new LinkedList<>();
      stack.push(1);
      int sign = 1;
      int i = 0;
      int len = s.length();
      int res = 0;
      while (i < len) {
        char c = s.charAt(i);
        switch (c) {
          case '(' -> stack.push(sign);
          case ')' -> stack.pop();
          case '+' -> sign = stack.peek();
          case '-' -> sign = -stack.peek();
          case ' ' -> {
          }
          default -> {
            int value = c - '0';
            while (++i < len && Character.isDigit(c = s.charAt(i))) {
              value = value * 10 + c - '0';
            }
            res += sign * value;
            i--;
          }
        }
        i++;
      }
      return res;
    }
  }

  /**
   * 他这个解法真滴好
   */
  static class copyff {
    public int calculate(String s) {
      Deque<Integer> q = new LinkedList<>();
      q.push(1);
      int sign = 1;
      int res = 0;
      int i = 0;
      for (char c : s.toCharArray()) {
        switch (c) {
          case ' ' -> {}
          case '(' -> q.push(sign);
          case ')' -> q.pop();
          case '+' -> sign = q.peek();
          case '-' -> sign = -q.peek();
          default -> {
            int num = 0;
            while (i < s.length() && Character.isDigit(s.charAt(i))) {
              num = num * 10 + s.charAt(i++) - '0';
            }
            i--;
            res += sign * num;
          }
        }
        i++;
      }
      return res;
    }
  }

  static class test {
    public static void main(String[] args) {
//      String s = " ( ( 1 ) + ( 4 + 5+2)-3)+(6+8) ";
      String s = "-(1)";
      Lexer lexer = new Lexer(s);
      Parser parser = new Parser(lexer);
      System.out.println(parser.cock());
    }

    public int calculate(String s) {
      return new Parser(new Lexer(s)).cock();
    }

    static final int eof = -1;
    static final int lpar = 0;
    static final int rpar = 1;
    static final int plus = 2;
    static final int minus = 3;
    static final int space = 4;
    static final int digit = 5;

    static class Token {
      Token(int type, int value) {
        this.type = type;
        this.value = value;
      }

      Token(int type) {
        this.type = type;
      }

      int type;
      int value;
    }

    static class Lexer {
      String text;
      int i;
      int len;
      Token cur;

      Lexer(String text) {
        this.text = text;
        len = text.length();
      }

      Token next() {
        if (i == len) {
          return new Token(eof);
        }
        char c = text.charAt(i++);
        switch (c) {
          case '(':
            return cur = new Token(lpar);
          case ')':
            return cur = new Token(rpar);
          case ' ':
            return cur = new Token(space);
          case '+':
            return cur = new Token(plus);
          case '-':
            return cur = new Token(minus);
          default:
            Token t = new Token(digit);
            int digit = c - '0';
            while (i < len && Character.isDigit(text.charAt(i))) {
              digit = digit * 10 + text.charAt(i++) - '0';
            }
            t.value = digit;
            return cur = t;
        }
      }
    }

    /**
     * expr := atom (expr' | epsilon)
     * expr' := ('+' | '-') expr
     * atom := par | digit
     * par := '(' expr ')'
     */
    static class Parser {
      Lexer lexer;

      Parser(Lexer lexer) {
        this.lexer = lexer;
      }

      Stmt parse() {
        return scanExpr();
      }

      int cock() {
        return parse().calc();
      }

      Expr2 scanExpr2(char op, Expr parent) {
        Expr2 expr2 = new Expr2();
        parent.children.add(expr2);
        expr2.op = op;
        expr2.right = scanAtom();
        return expr2;
      }

      /**
       * expr 是无数个 + - 组成
       */
      Expr scanExpr() {
        Expr expr = new Expr();
        expr.left = scanAtom();
        Token next = lexer.next();
        // 跳过开头空白
        while (next.type == space)
          next = lexer.next();
        while (next.type != eof) {
          switch (next.type) {
            case plus:
            case minus:
              scanExpr2(next.type == plus ? '+' : '-', expr);
              break;
            case rpar:
              return expr;
            default:
              throw new Error();
          }
          next = lexer.next();
          while (next.type == space)
            next = lexer.next();
        }
        return expr;
      }

      Atom scanAtom() {
        Token token = lexer.next();
        while (token.type == space)
          token = lexer.next();
        if (token.type != digit && token.type != lpar && token.type != minus) {
          throw new IllegalStateException("want ( or <digit> or -, got: " + token.type);
        }
        Atom atom = new Atom();
        int sign = 1;
        if (token.type == minus) {
          sign = -1;
          token = lexer.next();
        }
        if (token.type == digit) {
          atom.value = sign * token.value;
          return atom;
        }
        Par par = scanPar();
        par.sign = sign;
        atom.par = par;
        return atom;
      }

      Par scanPar() {
        Par par = new Par();
        par.expr = scanExpr();
        return par;
      }

    }

    static class Stmt {
      int calc() {
        throw new UnsupportedOperationException();
      }
    }

    static class Expr2 extends Stmt {
      char op;
      Atom right;
      Expr parent;
    }

    static class Expr extends Stmt {
      Atom left;
      List<Expr2> children = new ArrayList<>();

      @Override
      int calc() {
        if (children.isEmpty()) return left.calc();
        int res = left.calc();
        for (Expr2 child : children) {
          char op = child.op;
          Atom atom = child.right;
          if (op == '+') {
            res += atom.calc();
          } else {
            res -= atom.calc();
          }
        }
        return res;
      }
    }

    static class Atom extends Stmt {
      int value;
      Par par;

      int calc() {
        if (par != null) {
          return par.calc();
        }
        return value;
      }
    }

    static class Par extends Atom {
      int sign;
      Expr expr;

      @Override
      int calc() {
        return sign * expr.calc();
      }
    }

  }
}
